/*
   生成1～8的序列，要求，每个数字在相应的位置仅出现一次且必须出现一次；
   同时，相邻的数字序列在之前未出现过，例如：在前面出现过1，2，后面则不允许出现1，2
*/

#include <stdio.h>
#include <assert.h>
#include <algorithm>

const int N = 8;

int mate[20][N] = {0};
void print()
{
    printf("Sequence:\n");
    for (int i = 0; i < N; i++) {
        for (int k = 0; k < N; k++)
            printf("%4d,", mate[i][k]);
        printf("\n");
    }
}
int max = 5;
void place(int line)
{
    int num[N] = {1, 2, 3, 4, 5, 6, 7, 8};

    while(std::next_permutation(num, num + N)) {
        bool finished = true;
        // 在前面的行查找是否存在相同的序列
        for (int i = 0; i < line; i++) {
            for (int k = 0; k < N - 1; k++)
                for (int m = 0; m < N-1; m++) {
                    if (mate[i][k] == num[m] && mate[i][k+1] == num[m+1])
                        finished = false;
                }
        }
        // 同一数字不能出现在相同的位置
        for (int i = 0; i < line; i++)
            for (int k = 0; k < N; k++)
                if (mate[i][k] == num[k]) finished = false;
        // 如果满足，则找到一种排列
        if (finished) {
            // printf("No %d:", line);
            for (int i = 0; i < N; i++) {
                mate[line][i] = num[i];
                // printf("%3d", num[i]);
            }
            // printf("\n");
            place(line + 1);
        }
    }
    if (line > max) {
        printf("Max = %d\n", max);
        for (int i = 0; i < line; i++) {
            printf("No %d:", i);
            for (int k = 0; k < N; k++)
                printf("%3d", mate[i][k]);
            printf("\n");
        }
        max = line;
    }
}

int main()
{
    // 生成第一行
    for (int i = 0; i < N; i++)
        mate[0][i] = i + 1;
    place(1);
}
